package _2022.hot100._169_多数元素;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author： YHSimon
 * @date： 2022-05-08 09:40
 */
public class Solution {

    // 优化
    public int majorityElement3(int[] nums){

        int len=nums.length;
        int count=0;
        int ans=nums[0];
        for(int i=0;i<len;i++){
            if(nums[i]==ans){
                count++;
            }else{
                count--;
            }

            if(count==0){
                ans=nums[i];
                count=1;
            }
        }
        return ans;
    }
    public int majorityElement(int[] nums){

        int len=nums.length;
        Arrays.sort(nums);
        int count=0;
        int ans=nums[0];
        for(int i=0;i<len;i++){
            if(nums[i]==ans){
                count++;
            }else{
                count--;
                if(count==0){
                    ans=nums[i];
                    count=1;
                }
            }
        }
        return ans;
    }

    public int majorityElement2(int[] nums){
        int ans=nums[0];
        Map<Integer,Integer>  map=new  HashMap<>();
        int len=nums.length;
        for (int num : nums) {
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }

        for(Map.Entry<Integer,Integer> entry:map.entrySet()){
            if(entry.getValue()>(len/2)){
                ans=entry.getKey();
                break;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.majorityElement3(new int[]{1,1,2}));
    }
}
